/******************************************************
*This is Intermediate Code generated from PCAT code   *
*Group Member: Nguyen Pham Xuan Quynh   0712717       *
*              Luong Thanh Anh Duc      0712731       *
*Class 07CTT FIT University of Science                *
*Instructor: Vu Quoc Hoang FIT HCMUS                  *
******************************************************/


import java.util.*;

public class IRGen
{
	// declare the static variables which will be used
	
	static Integer[] staticLink = new Integer[100];
	static ArrayList numArg = new ArrayList();
	static String glb_parent = "";
	
	// list of string in the entire program
	static ArrayList strList = new ArrayList();
	
	// list of all label mark that it's the end of the loop
	// just use for the Exit Statement only 
	static ArrayList label_loop = new ArrayList();
	
	// store the current label in the program
	static Integer current_label = 0;
	
	// store the current variable order in the declaration section
	static Integer current_var_order = 0;
	
	// store the current procedure order in the declaration section 
	static Integer current_proc_order = 0;
	
	// store the current temporary variable order
	static Integer current_temp = 0;
	
	// store the current max temporary variable in a specific procedure
	static Integer max_temp = 0;
	
	
	// class Instruction is used to store the instruction
	static class Instruction
	{
		String ins;
		String op1;
		String op2;
		String op3;
		Instruction(String ins, String op1, String op2, String op3)
		{
			this.ins = ins;
			this.op1 = op1;
			this.op2 = op2;
			this.op3 = op3;
		}
		void genIRCode()
		{
			// op1, op2, op3 can be null
			if (ins.equals("proc"))
				System.out.println();
			System.out.print(ins);
			System.out.print(" ");
			if (op1 != null)
			{
				System.out.print(op1);
			}
			if(op2 != null)
			{
				System.out.print(", ");
				System.out.print(op2);
			}
			if(op3 != null)
			{
				System.out.print(", ");
				System.out.print(op3);
			}
			System.out.println();
		}
	}
	
/****************************************************************/	
/***********************Environment******************************/
/****************************************************************/

	static class Env 
	{
	    Ast.Dec dec;
	    Env next;

	    /** Empty environment is just a null Env. */
	    static final Env empty = null;

	    /** Creates new Env by extending an existing Env with a new declaration binding.
	     */
	    Env(Ast.Dec dec, Env next) 
		{
	    	this.dec = dec; 
	    	this.next = next;	      
	    }

	    public String toString() 
		{
	      String r = "[ ";
	      for (Env env = this; env != null; env = env.next) 
		  {
			r += env.dec + "\n";
	      }
	      r += "]";
	      return r;
	    }
	    static Env initEnv()
		{
			Env env = Env.empty;
			env = new VarEnv(new Ast.ConstDec("TRUE","BOOLEAN"), env, null, null);
		    env = new VarEnv(new Ast.ConstDec("FALSE", "BOOLEAN"), env, null, null);
		    env = new VarEnv(new Ast.ConstDec("NIL","?RECORD"), env, null, null);
		    return env;
		}
	}

	static class ProcEnv extends Env 
	{
		Env staticEnv;
		Integer order;
		final Integer depth; // the depth of the procedure // main procedure's depth is 0
		ProcEnv(Ast.Dec dec, Env staticEnv, Env next, Integer order, final Integer depth) 
		{
			super(dec,next); 
			this.staticEnv = staticEnv;
			this.order = order;
			this.depth = depth;
		}
	}
	static class VarEnv extends Env 
	{
	    Integer order;
	    final Integer depth; // the depth of the current procedure // main procedure's depth is 0
	    VarEnv(Ast.Dec dec, Env next, Integer order, final Integer depth) 
		{
	      super(dec,next); 
	      this.order = order;
	      this.depth = depth;
	    }
	}

	static Env find(String name,Env env) 
	{
		for (; env != null; env = env.next)
			if (env.dec.name.equals(name))
				return env;
		return null;
	}
/****************************************************************/	
/***********************Update Environment***********************/
/****************************************************************/
	
	// update the environmet
	static Env updateEnv(Ast.Decs d, final Env env, final Integer depth) 
	{
	    class DecsVisitor implements Ast.DecsVisitor 
		{
			public Object visit(Ast.VarDecs d)  
			{
				Env newEnv = env;
				for (int i = 0; i < d.vardeclist.length; ++i)
				{
					newEnv = new VarEnv(d.vardeclist[i],newEnv, current_var_order, depth);
					current_var_order++;
				}
				return newEnv;
			}
			// do nothing with typedecs
			public Object visit(Ast.TypeDecs d) 
			{		
				return env;  // just temporary
			}	

			public Object visit(Ast.ProcDecs d) 
			{
				Env newEnv = env;
				for(int i = 0; i < d.procdeclist.length; ++i)
				{
					newEnv = new ProcEnv(d.procdeclist[i], null, newEnv, current_proc_order, depth);
					current_proc_order++;
					numArg.add(d.procdeclist[i].formals.length);					
				}
				for(int i = 0; i < d.procdeclist.length; ++i)
				{
					ProcEnv temp = (ProcEnv)find(d.procdeclist[i].name, newEnv);
					temp.staticEnv = newEnv;
				}
				return newEnv;
			}
		}
	    try
	    {
	    	return (Env) d.accept(new DecsVisitor());
	    }
	    catch(Ast.Error err)
	    {
	    	return null; 
	    }	
	}
	// update the formal param to environment
	static Env updateEnv(Ast.FormalParam[] f, final Env env, final Integer depth)
	{
		Env newEnv = env;
		Integer iorder = 0;
		for (int i = 0; i < f.length; ++i)
		{
			newEnv = new VarEnv(f[i], newEnv, iorder, depth);
			iorder++;	
		}
		return newEnv;
	}

/*******************************************************************/	
/*****************Generate IR code**********************************/
/*******************************************************************/		

	static ArrayList gen(Ast.Program p)
	{
		numArg.add(0);
		
		// init environment
		Env env = Env.initEnv();
		
		// add main procedure to environment
		Ast.ProcDec main = new Ast.ProcDec(p.line, "main", null, new ArrayList(), p.body);
		env = new ProcEnv(main, null, env, 0, null);
		((ProcEnv)(find("main",env))).staticEnv = env;
		
		// increase current procedure order
		current_proc_order++;
		
		// generate IR for body
		ArrayList insList = gen(p.body, env, "_", "main", 0);
		
		if (strList.size() != 0)
			System.out.println();
		
		insList.add(0, new Instruction("entry", "main_0", null, null));
		
		for(int i = strList.size() - 1; i >= 0; --i)
		{
			insList.add(0, new Instruction("str", "\"" + (String)strList.get(i) + "\"", null, null));
		}
		
		return insList;
	}
	static ArrayList gen(Ast.Body b, Env env, String parent, String procname, final Integer depth)
	{
		glb_parent = parent;
		
		// update the environment before generate IR code
		Env newEnv = env;
		for (int i = 0; i < b.decslist.length; ++i)
		{
			newEnv = updateEnv(b.decslist[i], newEnv, depth);
		}
		Integer numVar = current_var_order; // store the number of variable in that procedure
		current_var_order = 0;
		procname += "_" + ((ProcEnv)(find(procname, env))).order.toString(); 
		
		ArrayList insList = new ArrayList();
		ArrayList insTemp = new ArrayList();
		
		
		for (int i = 0; i < b.decslist.length; ++i)
		{
			if (b.decslist[i] instanceof Ast.VarDecs)
			{
				// add the variable declaration in IR code
				insList.addAll(gen(b.decslist[i], newEnv, procname, depth));
			}
			else
			{
				// add other procedure declare inside this procedure in the temporary location
				insTemp.addAll(gen(b.decslist[i], newEnv, procname, depth));
			}
		}
		// add the body of procedure to IR code
		insList.addAll(gen(b.statement, newEnv, procname, depth));
		// add the information of procedure to IR code
		insList.add(0, new Instruction("proci", parent, numVar.toString(), max_temp.toString()));
		insList.add(0, new Instruction("proc", procname , null, null));
		insList.add(new Instruction("eproc", procname, null, null));
		
		// add procedure declaration inside
		insList.addAll(insTemp);
		
		Integer index = Integer.parseInt(procname.substring(procname.indexOf("_") + 1));
		if (parent.equals("_"))
			staticLink[0] = 0;
		else
			staticLink[index] = Integer.parseInt(parent.substring(parent.indexOf("_") + 1));
			
		
		return insList;
	}
	static ArrayList gen(Ast.Decs decs,final Env env, final String procname, final Integer depth)
	{
		class DecsVisitor implements Ast.DecsVisitor
		{
			public	Object visit(Ast.VarDecs decs) 
			{
				ArrayList insList = new ArrayList();
				for(int i = 0; i < decs.vardeclist.length; ++i)
				{
					insList.addAll(gen(decs.vardeclist[i],env, procname, depth));					
				}
				
				return insList;
			}
			public	Object visit(Ast.TypeDecs decs)
			{
				ArrayList insList = new ArrayList();
				return insList;
			}
			public	Object visit(Ast.ProcDecs decs) 
			{
				ArrayList insList = new ArrayList();
				Integer save = current_var_order;
				Integer save1 = current_temp;
				Integer save2 = max_temp;
				
				for (int i = 0; i < decs.procdeclist.length; ++i)
				{
					current_var_order = 0;
					current_temp = 0;
					max_temp = 0;
					insList.addAll(gen(decs.procdeclist[i], env, procname, depth));
				}
				current_var_order = save;
				current_temp = save1;
				max_temp = save2;
				return insList;	
			}
		}
		try
		{
			return (ArrayList)decs.accept(new DecsVisitor());
		}
		catch(Ast.Error err)
		{
			return null;
		}		
	}
	static ArrayList gen(Ast.Dec dec, final Env env, final String procname, final Integer depth)
	{
		class DecVisitor implements Ast.DecVisitor
		{
			public Object visit(Ast.VarDec dec) 
			{
				Integer old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				
				ArrayList temp = new ArrayList();
				
		
				temp = gen(dec.initializer,env, depth);
				
				String temp_var = (String)temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				Env variable = find(dec.name, env);
				
				insList.add(new Instruction("move", "@" + ((VarEnv)variable).order.toString() + "_" + dec.name, temp_var, null));
				
				current_temp = old_current_temp;
				return insList;
			}
			public Object visit(Ast.TypeDec dec)
			{
				ArrayList insList = new ArrayList();
				return insList;
			}
			public Object visit(Ast.ProcDec dec)
			{
				Env newEnv = updateEnv(dec.formals, env, depth + 1);
				
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				insList.addAll(gen(dec.body, newEnv, procname, dec.name, depth + 1));
						
				return insList;
			}
			public Object visit(Ast.ConstDec dec)
			{
				ArrayList insList = new ArrayList();	
				return insList;
			}
			public Object visit(Ast.FormalParam f)
			{	
				ArrayList insList = new ArrayList();
				return insList;
			}
		}
		try
		{
			return (ArrayList)dec.accept(new DecVisitor());
		}
		catch(Ast.Error err)
		{
			return null;
		}
	}
	static ArrayList gen(Ast.St st,final Env env, final String procname, final Integer depth)
	{
		class StVisitor implements Ast.StVisitor
		{
			public Object visit(Ast.SequenceSt s)  
			{				
				int old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				for (int i = 0; i < s.statements.length; ++i)
				{
					insList.addAll(gen(s.statements[i],env, procname, depth));
					current_temp = old_current_temp;
				}				
				return insList;
			}
			public Object visit(Ast.ReturnSt s)  
			{
				Integer old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				if (s.returnValue != null)
				{
					temp = gen(s.returnValue, env, depth);
				
					String var_return = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
				
					insList.addAll(temp);
					insList.add(new Instruction("retf",procname, var_return, null ));
				}
				else
					insList.add(new Instruction("ret",procname, null, null ));
				
				current_temp = old_current_temp;
				return insList;
			}
			public Object visit(Ast.ExitSt s)  
			{	
				ArrayList insList = new ArrayList();
				Integer label = (Integer)label_loop.get(label_loop.size() - 1);
				String target = "~" + label.toString();
				label_loop.remove(label_loop.size() - 1);
				
				insList.add(new Instruction("jump", target, null, null));
				
				return insList;
			}
			public Object visit(Ast.ForSt s)  
			{	
				Integer old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				String loopVar = null;
				//Get loopVar value x := 0
				Env var = find(s.loopVar, env);
				if (var.dec instanceof Ast.VarDec)
				{
					
					if (((VarEnv)var).depth == depth)
						loopVar = "@" + ((VarEnv)var).order.toString() + "_" + ((VarEnv)var).dec.name;
					else
					{
						loopVar = "$" + ((Integer)(depth - ((VarEnv)var).depth)).toString();
						loopVar += "_" + ((VarEnv)var).order.toString();
						loopVar += "_" + ((VarEnv)var).dec.name;
					}
				}
				else if (var.dec instanceof Ast.FormalParam)
					loopVar = "%" + ((VarEnv)var).order.toString() + "_" + ((VarEnv)var).dec.name;
				
				//Get stop value
				temp = gen(s.stop, env, depth);
				String stop = (String) temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				//Get start value
				temp = gen(s.start, env, depth);
				String start = (String) temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				insList.add(new Instruction("move", loopVar, start, null));
				
				//Get step value
				temp = gen(s.step, env, depth);
				String step = (String) temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				String label1 = "~" + current_label.toString();
				current_label++;
				
				label_loop.add(current_label);
				String label2 = "~" + current_label.toString();
				current_label++;
				
				insList.add(new Instruction(label1 + ":", null, null, null));
				
				insList.add(new Instruction("jlt", stop, loopVar, label2));
				
				//Body of ForSt
				temp = gen(s.body, env, procname, depth);
				insList.addAll(temp);
				
				insList.add(new Instruction("add", loopVar, loopVar, step));
				insList.add(new Instruction("jump", label1, null, null));
				
				insList.add(new Instruction(label2 + ":", null, null, null));
				
				current_temp = old_current_temp;
				return insList;
			}
			public Object visit(Ast.LoopSt s)  
			{	
				Integer old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				
				String label1 = "~" + current_label.toString();
				current_label++;
				insList.add(new Instruction(label1 + ":", null, null, null));
				
				label_loop.add(current_label);
				String op2 = "~" + current_label.toString(); 
				current_label++;				
				
				insList.addAll(gen(s.body, env, procname, depth));	
				
				insList.add(new Instruction("jump", label1, null, null));
				insList.add(new Instruction(op2 + ":", null, null, null));
				
				current_temp = old_current_temp; 
				return insList;
			}
			public Object visit(Ast.WhileSt s)  
			{	
				Integer old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				String label1 = "~" + current_label.toString();
				current_label++;
				
				label_loop.add(current_label);
				
				String label2 = "~" + current_label.toString();
				current_label++;
				
				insList.add(new Instruction(label1 + ":", null, null, null));
				

				temp = gen(s.test, env, depth);
				

				String test = (String) temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				current_temp = old_current_temp;
				
				insList.add(new Instruction("jf", test, label2, null));
								
				//Body of WhileSt
				insList.addAll(gen(s.body, env, procname, depth));
							
				insList.add(new Instruction("jump", label1, null, null));
				
				insList.add(new Instruction(label2 + ":", null, null, null));
				
				current_temp = old_current_temp;
				return insList;
			}
			public Object visit(Ast.IfSt s)  
			{
				Integer old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				String label1 = "~" + current_label.toString();
				current_label++;
				
				temp = gen(s.test, env, depth);
				
				String test = (String) temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				
				//Body of ifTrue statement
				insList.add(new Instruction("jf", test, label1, null));
				
				insList.addAll(gen(s.ifTrue, env, procname, depth));
				
				//if (((Ast.SequenceSt)s.ifFalse).statements.length == 0)
				if (!(s.ifFalse instanceof Ast.SequenceSt))
				{	
					String label2 = "~" + current_label.toString();
					current_label++;
						
					insList.add(new Instruction("jump", label2, null, null));
					
					insList.add(new Instruction(label1 + ":", null, null, null));
					
					current_temp = old_current_temp;
					//Body of ifFalse statement
					insList.addAll(gen(s.ifFalse, env, procname, depth));
	
					
					insList.add(new Instruction(label2 + ":", null, null, null));
				}
				else
				{
					if (((Ast.SequenceSt)s.ifFalse).statements.length == 0)
					{
						insList.add(new Instruction(label1 + ":", null, null, null));
					}
					else
					{
						String label2 = "~" + current_label.toString();
						current_label++;
							
						insList.add(new Instruction("jump", label2, null, null));
						
						insList.add(new Instruction(label1 + ":", null, null, null));
						
						current_temp = old_current_temp;
						//Body of ifFalse statement
						insList.addAll(gen(s.ifFalse, env, procname, depth));
		
						
						insList.add(new Instruction(label2 + ":", null, null, null));
					}
										
				}
			
				current_temp = old_current_temp;
				return insList;
			}
			
			public Object visit(Ast.WriteSt s)  
			{
				Integer old_current_temp = current_temp;
				if (strList.size() == 0)
					strList.add("\\n");
				
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				String temp_var = null;
				for (int i = 0; i < s.exps.length; ++i)
				{
					current_temp = old_current_temp;
					// the array list return from each expression will have the format:
					// 1. the list of instruction of that expression
					// 2. the temporary variable to be returned
					temp = gen(s.exps[i],env, depth);
					temp_var = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
							
					insList.add(new Instruction("write",temp_var, null, null));
				}
				insList.add(new Instruction("write","?0", null, null));
				current_temp = old_current_temp;
				return insList;
			}
			public Object visit(Ast.ReadSt s)  
			{
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
								
				String strTemp = "&" + current_temp.toString(); 
				current_temp++;
				Integer old_current_temp = current_temp;
				if(current_temp > max_temp)
					max_temp = current_temp;
				
				String var_read; // var to be read
				//Get targets var for ReadSt
				for (Integer i = 0; i < s.targets.length; ++i)
				{
					current_temp = old_current_temp;
					insList.add(new Instruction("read", strTemp, null, null));
					// when target is a variable
					if (s.targets[i] instanceof Ast.VarLvalue)
					{
						temp = gen(s.targets[i], env, depth);
						
						var_read = (String)temp.get(temp.size() - 1);
						temp.remove(temp.size() - 1);
						
						insList.addAll(temp);
						
						insList.add(new Instruction("move", var_read, strTemp, null));
					}
					// when target is an array
					else if (s.targets[i] instanceof Ast.ArrayDerefLvalue)
					{
						temp = gen(((Ast.ArrayDerefLvalue)s.targets[i]).index, env, depth);
						String index = (String)temp.get(temp.size() - 1);
						temp.remove(temp.size() - 1);
						insList.addAll(temp);
						
						temp = gen(((Ast.ArrayDerefLvalue)s.targets[i]).array, env, depth);
						String array = (String)temp.get(temp.size() - 1);
						temp.remove(temp.size() - 1);
						insList.addAll(temp);
						
						insList.add(new Instruction("arrs", array, index, strTemp));
					}
					// when target is a record
					else
					{
						Integer offset = ((Ast.RecordDerefLvalue)s.targets[i]).offset;
						
						temp = gen(((Ast.RecordDerefLvalue)s.targets[i]).record, env, depth);
						String temp_var = (String)temp.get(temp.size() - 1);
						temp.remove(temp.size() - 1);
						insList.addAll(temp);
						
						insList.add(new Instruction("recs", temp_var, offset.toString(), strTemp));
					}
				}
				current_temp = old_current_temp - 1;
				return insList;
			}
			public Object visit(Ast.CallSt s)  
			{
				Integer old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				String temp_var;
				
				Integer i;
				Env newEnv;
				for(i = 0; i < s.args.length; ++i)
				{
					current_temp = 0;
					temp = gen(s.args[i], env, depth);
					temp_var = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
					
					insList.add(new Instruction("arg", temp_var, i.toString(), null));
				}
				String proc = s.procName + "_" + ((ProcEnv)find(s.procName, env)).order.toString();
				
				insList.add(new Instruction("call", proc, i.toString(), null));
				current_temp = old_current_temp;
				return insList;
			}
			public Object visit(Ast.AssignSt s)  
			{
				Integer old_current_temp = current_temp;
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				temp = gen(s.rhs, env, depth);
				String op2 = (String)temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				String op1;
				
				// when left hand side is a variable
				if (s.lhs instanceof Ast.VarLvalue)
				{
					temp = gen(s.lhs, env, depth);
					op1 = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
		
					insList.add(new Instruction("move", op1, op2, null));
				}
				// when left hand side is an array
				else if (s.lhs instanceof Ast.ArrayDerefLvalue)
				{
					temp = gen(((Ast.ArrayDerefLvalue)s.lhs).index, env, depth);
					String index = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
					
					
					temp = gen(((Ast.ArrayDerefLvalue)s.lhs).array, env, depth);
					String array = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
					
					insList.add(new Instruction("arrs", array, index, op2));
					
				}
				// when left hand side is a record
				else if (s.lhs instanceof Ast.RecordDerefLvalue)
				{
					Integer offset = ((Ast.RecordDerefLvalue)s.lhs).offset;
					
					temp = gen(((Ast.RecordDerefLvalue)s.lhs).record, env, depth);
					String temp_var = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
					
					insList.add(new Instruction("recs", temp_var, offset.toString(), op2));
				}
				current_temp = old_current_temp;
				return insList;
			}
		}
		try
		{
			return (ArrayList)st.accept(new StVisitor());
		}
		catch(Ast.Error err)
		{
			return null;
		}
	}
	static ArrayList gen(Ast.Exp exp, final Env env, final Integer depth)
	{
		class ExpVisitor implements Ast.ExpVisitor
		{
			public Object visit(Ast.StringLitExp e)  
			{	
				// find the string in the stringlist
				Integer j;
				ArrayList insList = new ArrayList();
				for (j = 0; j < strList.size(); j++)
				{	
					if (((String)strList.get(j)).equals(e.lit))
					{	
						insList.add("?" + j.toString());
						break;
					}
				}
				// if string doesn't exist to the string list 
				// add it to the string list
				if (j == strList.size())
				{
					strList.add(e.lit);
					insList.add("?" + j.toString());
				}
				return insList;
			}
			public Object visit(Ast.RealLitExp e)  
			{
				// don't need to handle real expression
				ArrayList insList = new ArrayList();
				return insList;
			}
			public Object visit(Ast.BinOpExp e)  
			{
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				String op1 = null;	
				
				temp = gen(e.left, env, depth);
				String op2 = (String)temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				// normal case
				if ((e.binOp != Ast.AND) && (e.binOp != Ast.OR))
				{
					temp = gen(e.right, env, depth);
					String op3 = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);					

					if (op2.charAt(0) == '&')
					{
						op1 = op2;
						current_temp = Integer.parseInt(op2.substring(1)) + 1;
					}
					else if (op3.charAt(0) == '&')
					{
						op1 = op3;
						current_temp = Integer.parseInt(op3.substring(1)) + 1;
					}
					else
					{
						op1 = "&" + current_temp.toString();
						current_temp++;
						if (current_temp > max_temp)
							max_temp = current_temp;
					}
					
					String instruction;
					switch(e.binOp)
					{
						case Ast.AND:
							instruction = "and";
							break;
						case Ast.OR:
							instruction = "or";
							break;
						case Ast.PLUS:
							instruction = "add";
							break;
						case Ast.MINUS:
							instruction = "sub";
							break;
						case Ast.DIV:
							instruction = "div";
							break;
						case Ast.MOD:
							instruction = "mod";
							break;
						case Ast.SLASH:
							// use for real only
							instruction = "";
							break;
						case Ast.TIMES:
							instruction = "mult";
							break;
						case Ast.EQ:
							instruction = "eq";
							break;
						case Ast.NEQ:
							instruction = "neq";
							break;
						case Ast.GEQ:
							instruction = "gte";
							break;
						case Ast.GT:
							instruction = "gt";
							break;
						case Ast.LEQ:
							instruction = "lte";
							break;
						case Ast.LT:
							instruction = "lt";
							break;
						default:
							instruction = "add";
							break;
					}
					insList.add(new Instruction(instruction, op1, op2, op3));
				}	
				// short circuit for AND and OR operation
				else
				{	
					if (op2.charAt(0) == '&')
					{
						op1 = op2;
						current_temp = Integer.parseInt(op2.substring(1)) + 1;
					}
					else
					{
						op1 = "&" + current_temp.toString();
						current_temp++;
						if (current_temp > max_temp)
							max_temp = current_temp;
					}
					
					insList.add(new Instruction("move", op1, op2, null));
					
					String label = "~" + current_label.toString();
					current_label++;
					if (e.binOp == Ast.AND)
						insList.add(new Instruction("jf", op1, label, null));
					else
						insList.add(new Instruction("jt", op1, label, null));
					
					temp = gen(e.right, env, depth);
					String op3 = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
					
					insList.add(new Instruction("move", op1, op3, null));
					insList.add(new Instruction(label + ":", null, null, null));
					
				}
				insList.add(op1);
				return insList;
			}
			public Object visit(Ast.UnOpExp e)  
			{
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				temp = gen(e.operand, env, depth);
				String op2 = (String)temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				insList.addAll(temp);
				
				String instruction = null;
				switch(e.unOp)
				{
					case Ast.NOT:
						instruction = "not";	
						break;
						
					case Ast.UMINUS:
						instruction = "comp";					
						break;
				}
				
				String op1;
				if (op2.charAt(0) == '&')
				{
					op1 = op2;
					current_temp = Integer.parseInt(op2.substring(1)) + 1;
				}
				else
				{
					op1 = "&" + current_temp.toString();
					current_temp++;
					if (current_temp > max_temp)
						max_temp = current_temp;
				}
				
				insList.add(new Instruction (instruction, op1, op2, null));
				insList.add(op1);
				
				return insList;
			}
			public Object visit(Ast.LvalExp e)  
			{
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				String temp_var;
				
				temp = gen(e.lval, env, depth);
				temp_var = (String)temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				
				insList.addAll(temp);
				insList.add(temp_var); // add to list the lvalue
				
				return insList;
			}
			public Object visit(Ast.CallExp e)  
			{
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				String temp_var = null;
				String var_return = null;
				boolean flag = false;
				Integer i;
				for(i = 0; i < e.args.length; ++i)
				{
					temp = gen(e.args[i], env, depth);
					temp_var = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
					
					if ((flag == false) && (temp_var.charAt(0) == '&'))
					{
						var_return = temp_var;
						flag = true;
					}
					
					insList.add(new Instruction("arg", temp_var, i.toString(), null));
				}
				String proc = e.procName + "_" + ((ProcEnv)find(e.procName, env)).order.toString();
				
				if (var_return == null)
				{
					var_return = "&" + current_temp.toString();
					current_temp++;
					if (current_temp > max_temp)
						max_temp = current_temp;
				}
				else
				{
					current_temp = Integer.parseInt(var_return.substring(1)) + 1;
				}
				
				
				insList.add(new Instruction("callf", var_return, proc, i.toString()));
				insList.add(var_return); // return the variable which we want to return
				return insList;
			}
			public Object visit(Ast.ArrayExp e)  
			{	
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				Integer i = 0; 
				
				ArrayList count_exp_list = new ArrayList();
				ArrayList value_exp_list = new ArrayList();
				
				String array_var = "&" + current_temp.toString();
				current_temp++;
				if (current_temp > max_temp)
					max_temp = current_temp;
				
				for (i = 0; i < e.initializers.length; ++i)
				{
					temp = gen(e.initializers[i], env, depth);
					
					value_exp_list.add(temp.get(temp.size() - 1));
					temp.remove(temp.size() - 1);
					
					count_exp_list.add(temp.get(temp.size() - 1));
					temp.remove(temp.size() - 1);
					
					insList.addAll(temp);
				}
				
				String total_length_var = "&" + current_temp.toString();
				current_temp++;
				String index_var = "&" + current_temp.toString();
				current_temp++;	
				if (current_temp > max_temp)
					max_temp = current_temp;
				
				insList.add(new Instruction("move", total_length_var, "0", null));
				for (i = 0; i < count_exp_list.size(); ++i)
				{
					insList.add(new Instruction("jlte", (String)count_exp_list.get(i), "0", "~" + current_label.toString()));
					insList.add(new Instruction("add", total_length_var, total_length_var, (String)count_exp_list.get(i)));
					insList.add(new Instruction("~" + current_label.toString() + ":", null, null, null));
					current_label++;
				}
				
				insList.add(new Instruction("arra", array_var, total_length_var, null));
				insList.add(new Instruction("move", index_var, "0", null));
				
				for (i = 0; i < count_exp_list.size(); ++i)
				{
					insList.add(new Instruction("jlte", (String)count_exp_list.get(i),"0", "~" + ((Integer)(current_label + 1)).toString()));
					insList.add(new Instruction("move", total_length_var, "0", null));
					insList.add(new Instruction("~" + current_label.toString() + ":", null, null, null));
					current_label++;
					
					insList.add(new Instruction("jeq", total_length_var, (String)count_exp_list.get(i), "~" + current_label.toString()));
					insList.add(new Instruction("arrs", array_var, index_var, (String)value_exp_list.get(i)));
					
					insList.add(new Instruction("add", total_length_var, total_length_var, "1"));
					insList.add(new Instruction("add", index_var, index_var, "1"));
					insList.add(new Instruction("jump", "~" + ((Integer)(current_label - 1)).toString(), null, null));
					
					insList.add(new Instruction("~" + current_label.toString() + ":", null, null, null));
					current_label++;
				}
				
				current_temp = Integer.parseInt(array_var.substring(1)) + 1;
				
				insList.add(array_var); // return the location of array
				return insList;
			}
			public Object visit(Ast.RecordExp e)  
			{	
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				Integer offset = 0;
				String temp_var;
				String var_return = "&" + current_temp.toString();
				current_temp++;
				if (current_temp > max_temp)
					max_temp = current_temp;
				
				insList.add(new Instruction("reca", var_return, ((Integer)(e.initializers.length)).toString(), null));
				for (int i = 0; i < e.initializers.length; ++i)
				{
					temp = gen(e.initializers[i], env, depth);
					temp_var = (String)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					offset = (Integer)temp.get(temp.size() - 1);
					temp.remove(temp.size() - 1);
					insList.addAll(temp);
					insList.add(new Instruction("recs", var_return, offset.toString(), temp_var));
				}
				
				insList.add(var_return); // return the location of record
				
				return insList;
			}
			public Object visit(Ast.IntLitExp e)  
			{
				// just return that number in string format
				ArrayList insList = new ArrayList();
				insList.add(((Integer)e.lit).toString());
				return insList;
			}
		}
		try
		{
			return (ArrayList)exp.accept(new ExpVisitor());
		}
		catch(Ast.Error err)
		{ 
			return null;
		}
		
		
	}
	static ArrayList gen(Ast.Lvalue lval, final Env env, final Integer depth)
	{
		class LvalueVisitor implements Ast.LvalueVisitor
		{
			public Object visit(Ast.VarLvalue l) 
			{
				ArrayList insList = new ArrayList();
				
				Env var = find(l.name, env);
				if (var.dec instanceof Ast.VarDec)
				{
					// when lvalue is variable in the same depth
					if (((VarEnv)var).depth == depth)
						insList.add("@" + ((VarEnv)var).order.toString() + "_" + ((VarEnv)var).dec.name);
					// when lvalue is variable in the different depth
					else
					{
						String IR_var_name = "$" + ((Integer)(depth - ((VarEnv)var).depth)).toString();
						IR_var_name += "_" + ((VarEnv)var).order.toString();
						IR_var_name += "_" + ((VarEnv)var).dec.name;
						insList.add(IR_var_name);
					}
				}
				if (var.dec instanceof Ast.FormalParam)
					// when lvalue is formal parameters
					insList.add("%" + ((VarEnv)var).order.toString() + "_" + ((VarEnv)var).dec.name);
				if (var.dec instanceof Ast.ConstDec)
				{	// when lvalue is constant
					if (((Ast.ConstDec)var.dec).name.equals("TRUE"))
						insList.add("1");
					if (((Ast.ConstDec)var.dec).name.equals("FALSE"))
						insList.add("0");
					if (((Ast.ConstDec)var.dec).name.equals("NIL"))
						insList.add("0");
				}
				
				return insList;
			}
			public Object visit(Ast.ArrayDerefLvalue l) 
			{	
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				String var_return = "&" + current_temp.toString();
				current_temp++;
				if (current_temp > max_temp)
					max_temp = current_temp;
				
				temp = gen(l.index, env, depth);
				
				String index = (String)temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				
				insList.addAll(temp);
				
				temp = gen(l.array, env, depth);
				
				String array = (String)temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				
				insList.addAll(temp);
				
				insList.add(new Instruction("arrg", var_return, array, index));
				insList.add(var_return); // return the location of array
				
				return insList;
			}
			public Object visit(Ast.RecordDerefLvalue l) 
			{
				ArrayList insList = new ArrayList();
				ArrayList temp = new ArrayList();
				
				String var_return = "&" + current_temp.toString();
				current_temp++;
				if (current_temp > max_temp)
					max_temp = current_temp;
				
				temp = gen(l.record, env, depth);
				
				String op2 = (String)temp.get(temp.size() - 1);
				temp.remove(temp.size() - 1);
				
				insList.addAll(temp);
				
				insList.add(new Instruction("recg",var_return, op2, ((Integer)l.offset).toString()));
				insList.add(var_return); // return the location of record
				
				return insList;
			}
		}
		try
		{
			return (ArrayList)lval.accept(new LvalueVisitor());
		}
		catch(Ast.Error err)
		{
			return null;
		}
	}
	// return value:
	// 1. instruction list
	// 2. offset of that field in record
	// 3. temporary value to be assigned
	static ArrayList gen(Ast.RecordInit init, Env env, final Integer depth)
	{
		ArrayList insList = new ArrayList();
		ArrayList temp = new ArrayList();
		
		
		temp = gen(init.value, env, depth);
		
		String temp_var =  (String)temp.get(temp.size() - 1);
		temp.remove(temp.size() - 1);
		
		if (temp_var.charAt(0) == '&')
		{
			current_temp = Integer.parseInt(temp_var.substring(1)) + 1;
		}
		
		insList.addAll(temp);
		insList.add(init.offset);
		insList.add(temp_var);
		
		return insList;
	}	
	
	// return value:
	// 1. Instruction list
	// 2. Temporary variable for count expression
	// 3. Temporary variable for value expression
	static ArrayList gen(Ast.ArrayInit init, Env env, final Integer depth)
	{
		ArrayList insList = new ArrayList();
		ArrayList temp = new ArrayList();
		
		String count_var;
		String value_var;
		
		temp = gen(init.count, env, depth);
		count_var =  (String)temp.get(temp.size() - 1);
		temp.remove(temp.size() - 1);
		
		insList.addAll(temp);
		
		
		if (count_var.charAt(0) == '&')
		{
			current_temp = Integer.parseInt(count_var.substring(1)) + 1;
		}
		
		temp = gen(init.value, env, depth);
		value_var =  (String)temp.get(temp.size() - 1);
		temp.remove(temp.size() - 1);
		
		insList.addAll(temp);
		
		
		if (value_var.charAt(0) == '&')
		{
			current_temp = Integer.parseInt(value_var.substring(1)) + 1;
		}
		
		insList.add(count_var);
		insList.add(value_var);
		
		return insList;
	}
}